package jasymca;
/* Jasymca	-	- Symbolic Calculator for Mobile Devices
 This version is written for J2ME, CLDC 1.1,  MIDP 2, JSR 75
 or J2SE


 Copyright (C) 2006 - Helmut Dersch  der@hs-furtwangen.de

 This program is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2, or (at your option)
 any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */

/*------------------------------------------------------------*/

import java.util.Vector;

public abstract class Algebraic {
  // Build polynomial expression using Horner's method
  public static Algebraic horner(Variable x, Algebraic[] c)
      throws JasymcaException {
    return horner(x, c, c.length);
  }
  // Build polynomial expression using Horner's method
  public static Algebraic horner(Variable x, Algebraic[] c, int n)
      throws JasymcaException {
    if (n == 0)
      return Zahl.ZERO;
    Polynomial X = new Polynomial(x);
    Algebraic p = c[n - 1];
    for (int i = n - 2; i >= 0; i--)
      p = p.mult(X).add(c[i]);
    return p;
  }
  public static void p(String s) {
    Lisp.p(s);
  }
  public abstract Algebraic add(Algebraic x) throws JasymcaException;
  public Algebraic cc() throws JasymcaException {
    throw new JasymcaException("cc not implemented for " + this);
  }
  Algebraic coefficient(Variable r, int i) {
    if (this instanceof Polynomial && ((Polynomial) this).var.equals(r))
      return ((Polynomial) this).coefficient(i);
    if (i == 0)
      return this;
    else
      return Zahl.ZERO;
  }

  public boolean constantq() throws JasymcaException {
    CountVars c = new CountVars();
    c.f_exakt(this);
    return c.v.size() == 0;
  }

  // Davenport, p133
  public Algebraic content(Variable r) throws JasymcaException {
    if (this instanceof Zahl)
      return this;
    Algebraic result = coefficient(r, 0);
    for (int i = 0; i <= degree(r) && !result.equals(Zahl.ONE); i++)
      result = result.poly_gcd(coefficient(r, i));
    return result;
  }

  int degree(Variable r) {
    if (this instanceof Polynomial && ((Polynomial) this).var.equals(r))
      return ((Polynomial) this).degree();
    return 0;
  }

  // Loke depends, but does not recurse into functions
  public boolean depdir(Variable var) {
    return false;
  }

  public boolean depends(Variable var) {
    return false;
  }
  public abstract Algebraic deriv(Variable var) throws JasymcaException;

  public abstract Algebraic div(Algebraic x) throws JasymcaException;
  // Divide 2 Polynomials with rest, overwritten in Polynomial && Zahl
  public Algebraic[] div(Algebraic q1, Algebraic[] result)
      throws JasymcaException {
    return result;
  }

  public Algebraic divrest(Algebraic q) throws JasymcaException {
    return div(q, null)[1];
  }
  @Override
  public abstract boolean equals(Object x);

  public Algebraic euclid(Algebraic q, Variable r) throws JasymcaException {
    // p,q are numbers or polynomials
    // Alles bezogen auf Variable r !
    int dp = degree(r);
    int dq = q.degree(r);
    Algebraic a = dp < dq
        ? this
        : mult(q.coefficient(r, dq).pow_n(dp - dq + 1));
    Algebraic b = q;
    Algebraic c = a.mod(b, r);
    return c.equals(Zahl.ZERO) ? b : b.euclid(c, r);
  }

  public Algebraic imagpart() throws JasymcaException {
    return sub(cc()).div(Zahl.TWO).div(Zahl.IONE);
  };

  public abstract Algebraic integrate(Variable var) throws JasymcaException;

  public Algebraic map(LambdaAlgebraic f) throws JasymcaException {
    throw new JasymcaException("Map not implemented for " + this);
  }

  // this modulo q (polynomial division)
  public Algebraic mod(Algebraic q, Variable r) throws JasymcaException {
    int len = degree(r) - q.degree(r);
    if (len < 0)
      return this;
    Algebraic[] cdiv = new Algebraic[len + 1];
    Algebraic[] nom = new Algebraic[degree(r) + 1];
    for (int i = 0; i < nom.length; i++)
      nom[i] = coefficient(r, i);
    Algebraic den = q.coefficient(r, q.degree(r));
    for (int i = len, k = nom.length - 1; i >= 0; i--, k--) {
      cdiv[i] = nom[k].polydiv(den);
      nom[k] = Zahl.ZERO;
      for (int j = k - 1, l = q.degree(r) + 1 - 2; j > k - (q.degree(r) + 1); j--, l--)
        nom[j] = nom[j].sub(cdiv[i].mult(q.coefficient(r, l)));
    }
    return horner(r, nom, nom.length - 1 - len);
  }

  public abstract Algebraic mult(Algebraic x) throws JasymcaException;

  public abstract double norm();

  // Davenport, p133
  public Algebraic poly_gcd(Algebraic q) throws JasymcaException {
    // poly_gcd does not work with Exponential simplifications
    if (Exponential.containsexp(this) || Exponential.containsexp(q)) {
      DeExp dx = new DeExp();
      return new NormExp().f_exakt(dx.f_exakt(this).poly_gcd(dx.f_exakt(q)));
    }
    if (equals(Zahl.ZERO))
      return q;
    if (q.equals(Zahl.ZERO))
      return this;
    if (this instanceof Zahl || q instanceof Zahl)
      return Zahl.ONE;
    // r is the mainest of the two variables
    Variable r = ((Polynomial) q).var.smaller(((Polynomial) this).var)
        ? ((Polynomial) this).var
        : ((Polynomial) q).var;
    Algebraic pc = content(r), qc = q.content(r);
    Algebraic eu = polydiv(pc).euclid(q.polydiv(qc), r);
    Algebraic re = eu.polydiv(eu.content(r)).mult(pc.poly_gcd(qc));
    // return re;
    if (re instanceof Zahl)
      return Zahl.ONE;
    Polynomial rp = (Polynomial) re;
    if (rp.coef[rp.degree()] instanceof Zahl)
      return rp.div(rp.coef[rp.degree()]); // Normalize Polynomial
    return rp;
  }

  // //////////////// GCD routines adapted from Davenports book
  // /////////////////

  // this div q (polynomial division)
  public Algebraic polydiv(Algebraic q1) throws JasymcaException {
    if (q1 instanceof Zahl)
      return div(q1);
    if (equals(Zahl.ZERO))
      return Zahl.ZERO;
    if (!(this instanceof Polynomial) || !(q1 instanceof Polynomial))
      throw new JasymcaException(
          "Polydiv is implemented for polynomials only.Got " + this + " / "
              + q1);
    Polynomial p = (Polynomial) this;
    Polynomial q = (Polynomial) q1;
    if (p.var.equals(q.var)) {
      int len = p.coef.length - q.coef.length;
      if (len < 0)
        throw new JasymcaException("Polydiv requires zero rest.");
      Algebraic[] cdiv = new Algebraic[len + 1];
      Algebraic[] nom = p.clone(p.coef);
      Algebraic den = q.coef[q.coef.length - 1];
      for (int i = len, k = nom.length - 1; i >= 0; i--, k--) {
        cdiv[i] = nom[k].polydiv(den);
        nom[k] = Zahl.ZERO;
        for (int j = k - 1, l = q.coef.length - 2; j > k - q.coef.length; j--, l--)
          nom[j] = nom[j].sub(cdiv[i].mult(q.coef[l]));
      }
      return horner(p.var, cdiv);
    } else {
      Algebraic[] cn = new Algebraic[p.coef.length];
      for (int i = 0; i < p.coef.length; i++)
        cn[i] = p.coef[i].polydiv(q1);
      return horner(p.var, cn);
    }
  }

  public Algebraic pow_n(int n) throws JasymcaException {
    if (n == 0)
      return Zahl.ONE;
    if (n < 0)
      return Zahl.ONE.div(pow_n(-n));
    Algebraic result = this;
    for (int i = 1; i < n; i++)
      result = mult(result);
    return result;
  }

  public Algebraic rat() throws JasymcaException {
    return new LambdaRAT().f_exakt(this);
  }

  public Algebraic realpart() throws JasymcaException {
    return add(cc()).div(Zahl.TWO);
  }

  public Algebraic reduce() throws JasymcaException {
    return this;
  }

  public Algebraic sub(Algebraic x) throws JasymcaException {
    return add(x.mult(Zahl.MINUS));
  }

  public Object toPrefix() {
    return this;
  }

  // //////////////////////////////////////////////////////////////////////////////////////

  public Algebraic value(Variable var, Algebraic x) throws JasymcaException {
    return this;
  }

}

// Count number of Simple Variables (no Constants!)
class CountVars extends LambdaAlgebraic {
  Vector<Variable> v;
  public CountVars() {
    v = new Vector<Variable>();
  }

  @Override
  Algebraic f_exakt(Algebraic f) throws JasymcaException {
    if (f instanceof Polynomial) {
      Polynomial x = (Polynomial) f;
      if (x.var instanceof SimpleVariable && !(x.var instanceof Constant))
        if (!v.contains(x.var))
          v.addElement(x.var);
    }
    f.map(this);
    return Zahl.ZERO;
  }
}
